package org.lql.algo.codecrush.week003;

import org.lql.algo.common.ListNode;

/**
 * @author: liangqinglong
 * @date: 2025-07-30 15:46
 * @description: 160. 相交链表 <a href="https://leetcode.cn/problems/intersection-of-two-linked-lists/description/">...</a>
 **/
public class GetIntersectionNode {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null; // 任何一个链表为空，肯定没有交点
        }

        ListNode p = headA; // 指针 p 从 A 开始走
        ListNode q = headB; // 指针 q 从 B 开始走

        // 两个指针以相同速度遍历，如果相交，一定会在交点相遇
        while (p != q) {
            // 如果 p 走到末尾，则跳到 headB 继续走
            p = (p == null) ? headB : p.next;

            // 如果 q 走到末尾，则跳到 headA 继续走
            q = (q == null) ? headA : q.next;
        }

        // 如果有交点，p 和 q 会在交点相遇；否则会一起变成 null（走完整个链表后）
        return p;
    }

    public static void main(String[] args) {
        // 公共部分：8 → 4 → 5
        ListNode common = new ListNode(8);
        common.next = new ListNode(4);
        common.next.next = new ListNode(5);

        // 链表 A：4 → 1 → [8 → 4 → 5]
        ListNode headA = new ListNode(4);
        headA.next = new ListNode(1);
        headA.next.next = common; // 相交

        // 链表 B：5 → 6 → 1 → [8 → 4 → 5]
        ListNode headB = new ListNode(5);
        headB.next = new ListNode(6);
        headB.next.next = new ListNode(1);
        headB.next.next.next = common; // 相交

        GetIntersectionNode getIntersectionNode = new GetIntersectionNode();
        ListNode intersectionNode = getIntersectionNode.getIntersectionNode(headA, headB);
        printList(intersectionNode); // 应该从8开始打印：8 → 4 → 5
    }

    public static void printList(ListNode head) {
        while (head != null) {
            System.out.print(head.val);
            if (head.next != null) {
                System.out.print(" -> ");
            }
            head = head.next;
        }
        System.out.println();
    }


}
